#include <iostream>
using namespace std;

namespace DateStruct
{
	struct BinaryTreeDate
	{
		int key;
		BinaryTreeDate *parent;
		BinaryTreeDate *left;
		BinaryTreeDate *right;
		BinaryTreeDate(int Key) :key(Key), left(nullptr), right(nullptr), parent(nullptr){}
	};

	BinaryTreeDate *TreeSearch(BinaryTreeDate *root, int val)
	{
		if (root == nullptr)
			return root;

		if (val > root->key)
			return TreeSearch(root->right, val);
		else if (val < root->key)
			return TreeSearch(root->left, val);

		return root;
	}

	BinaryTreeDate *TreeSearchNotRecursion(BinaryTreeDate *root, int val)
	{
		while (root != nullptr && root->key != val)
		{
			if (val > root->key)
				root = root->right;
			else
				root = root->left;
		}
		return root;
	}

	BinaryTreeDate *TreeMaxSearch(BinaryTreeDate *root)
	{
		while (root->right != nullptr)
			root = root->right;

		return root;
	}

	BinaryTreeDate *TreeMinSearch(BinaryTreeDate *root)
	{
		while (root->left != nullptr)
			root = root->left;

		return root;
	}

	BinaryTreeDate *TreeMinRecursionSearch(BinaryTreeDate *root)
	{
		if (root->left == nullptr)
			return root;
		else
			return TreeMinRecursionSearch(root->left);
	}

	BinaryTreeDate *TreeMaxRecursionSearch(BinaryTreeDate *root)
	{
		if (root->right == nullptr)
			return root;
		else
			return TreeMaxRecursionSearch(root);
	}

	BinaryTreeDate *TreeNodeSuccessor(BinaryTreeDate *Node)
	{
		if (Node->right != nullptr)
			return TreeMinRecursionSearch(Node->right);//向下查找

		//向上查找
		BinaryTreeDate *parent = Node->parent;
		while (parent != nullptr && parent->right == Node)
			//若为左节点则表明parent就是其大节点集合中最小的一个
		{
			Node = parent;
			parent = parent->parent;
		}
		return parent;
	}

	BinaryTreeDate *TreeNodePredecessors(BinaryTreeDate *Node)
	{
		if (Node->left != nullptr)
			return TreeMaxRecursionSearch(Node->left);//向下查找

		BinaryTreeDate *parent = Node->parent;
		while (parent != nullptr && parent->left == Node)
			//若为右节点则表明parent就是其小节点集合中最大的一个
		{
			Node = parent;
			parent = parent->parent;
		}
		return parent;
	}

	void TreeInsert(BinaryTreeDate *root, BinaryTreeDate *NewNode)
	{
		BinaryTreeDate *p = root;
		BinaryTreeDate *parent = nullptr;
		while (p != nullptr)
		{
			parent = p;
			if (NewNode->key > p->key)
				p = p->right;
			else
				p = p->left;
		}
		NewNode->parent = parent;
		if (parent == nullptr)
			root = NewNode;
		else if (NewNode->key > parent->key)
			parent->right = NewNode;
		else
			parent->left = NewNode;
	}

	//更改结点
	void TreeTransition(BinaryTreeDate *root, BinaryTreeDate *Node, BinaryTreeDate *T)
	{
		if (Node->parent == nullptr)//表明要删除的结点为root结点
			root = T;
		else
		if (Node->parent->left == Node)
			Node->parent->left = T;
		else
			Node->parent->right = T;

		if (T != nullptr)
			T->parent = Node->parent;
	}

	void TreeDeleteNode(BinaryTreeDate *root, BinaryTreeDate *Node)
	{
		if (Node->left == nullptr)
			TreeTransition(root, Node, Node->right);
		else
		if (Node->right == nullptr)
			TreeTransition(root, Node, Node->left);
		else
		{
			//左右两棵树都不为nullptr
			//更改的为右子树
			BinaryTreeDate *Successor = TreeMinRecursionSearch(Node->right);//获得后继
			if (Successor->parent != Node)//表明Successor->left为空,Successor->right可能不为空
			{
				TreeTransition(root, Successor, Successor->right);//处理Successor->right
				//这个时候Successor已经变为单独Node，Successor->left

				Successor->right = Node->right;//更改
				Successor->right->parent = Successor;
			}
			TreeTransition(root, Node, Successor);//处理Node的parent Node使其指向 Successor并让Successor->parent = Node->parent

			//处理Node->left结点
			Successor->left = Node->left;
			Successor->left->parent = Successor;
		}
		delete Node;//释放结点z
	}

	void TreeInsertNotRecursion(BinaryTreeDate *&root, BinaryTreeDate *NewNode)
	{
		BinaryTreeDate *T = root;
		if (T == nullptr)
			root = NewNode;
		else
		{
			if (NewNode->key > T->key)
				TreeInsertNotRecursion(T->right, NewNode);
			else
				TreeInsertNotRecursion(T->left, NewNode);
			if (NewNode->parent == nullptr)//只有第一次赋值时才是其真正parent结点
				NewNode->parent = T;
		}
	}
}

int main()
{
	using namespace DateStruct;

	BinaryTreeDate *p = nullptr;
	BinaryTreeDate *Node = new BinaryTreeDate(20);
	BinaryTreeDate *Node1 = new BinaryTreeDate(22);
	BinaryTreeDate *Node2 = new BinaryTreeDate(22);
	TreeInsertNotRecursion(p, Node);
	TreeInsertNotRecursion(p, Node1);
	TreeInsertNotRecursion(p, Node2);
	delete Node;
	delete Node1;
	delete Node2;
	return 0;
}